package com.zll.study;

/**
 * 描述
 * 给你一个文本串 T ，一个非空模板串 S ，问 S 在 T 中出现了多少次
 *
 * 数据范围：1 \le len(S) \le 500000, 1 \le len(T) \le 10000001≤len(S)≤500000,1≤len(T)≤1000000
 * 要求：空间复杂度 O(len(S))O(len(S))，时间复杂度 O(len(S)+len(T))O(len(S)+len(T))
 *
 * 输入：
 * "ababab","abababab"
 * 返回值：
 * 2
 */
public class NC149kmp算法 {
    public static void main(String[] args) {
        kmp("ababab","abababab");
    }

    public static int kmp (String S, String T) {
        // write code here
        int count = 0;
        int[] next = new int[S.length()];
        getNext(S, next);
        for (int i = 0, j = 0; i < T.length(); ++i) {
            if (j > 0 && S.charAt(j) != T.charAt(i)) {
                j = next[j - 1];
            }
            if (S.charAt(j) == T.charAt(i)) {
                j++;
            }
            if (j == S.length()) {
                count++;
                j = next[j-1];
            }
        }
        return count;
    }
    public static void getNext(String s, int[] next) {
        int i = 1, j = 0;
        for (; i < s.length(); ++i) {
            if (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }
}
